Large projects, inventories, and organizations typically necessitate a correspondingly large information infrastructure. This information infrastructure often includes large amounts of data that can be represented logically in a hierarchical fashion. For example, a book store may electronically organize its inventory hierarchically (e.g., first by genre, then by author, then by title). Hierarchical data structures are also used elsewhere to organize data (e.g., project scheduling, organizational charts, etc.).
Organizing data in a hierarchical fashion is commonly handled by storing the data in tree data structures. Tree management software allows users to store hierarchically organized data as logical trees in relational databases. For example, using tree management software, a user can define an organizational chart for his business that shows, for each department of the business, which employees work in that department. To do so, the user specifies parent-child relationships between database entries. A parent-child relationship defines the connection between an upper-level node in the tree with the node's direct descendants. After parent-child relationships have been defined, nodes can be inserted into the tree.
A book store inventory example might be considered for illustrative purposes. A book store inventory can be stored in a tree-like structure. To store such a structure, a user uses tree management software to define the tree data structure, including parent-child relationships between nodes. The tree data structure for the book store inventory begins with a root node that represents the overall book store inventory. Underneath the root node, the user can use the tree management software to subdivide the inventory into genres by creating child nodes representing specific genres of books (e.g., “fiction,” “history,” “fantasy,” etc.). The user can then categorize the inventory according to author name by creating, under each of the genre nodes, child nodes that represent authors. At the lowest level of the tree, the user defines what a leaf node looks like (e.g., a node that lists a book title, price, and availability) and then adds leaf nodes to the tree based on what is actually in the book store's physical inventory.
Large organizations often use more than one separate hierarchical structure to represent and manage different sets of related information. For example, cost information, scheduling information, and work flow data may be related to each other in the real-world, yet each set of information is often stored in a separate hierarchical structure. For instance, a business accounting department may need access to scheduling, resources, and labor costs, to insure that sufficient funds are available to meet payroll. Unfortunately, for a variety of reasons (e.g., confidentiality and data management), businesses often use disparate hierarchical structures to represent disparate data.
These approaches suffer from some problems. Typically, for each node in a hierarchy, the parent-child relationship information is physically stored in a location separate from the underlying data sources. This can become expensive in terms of the computer resources used. In other words, storing all children for a parent in a separate hierarchy becomes expensive storage-space wise. It is also often labor-intensive to maintain the same information in separate locations.
Current hierarchical data representations and approaches for managing such data representations suffer from a number of disadvantages that become apparent as the size and complexity of those representations increase. For example, scheduling software might be used to manage project deadlines. When a single job or operation within the hierarchy is modified, delayed, or canceled, the estimated start and completion dates of all subsequent operations might need to be re-computed serially before the final completion date of the project can be made available. Similarly, should the cost of any individual sub-assembly of a larger manufactured item change, the cost of an entire item that includes that sub-assembly might need to be re-calculated by traversing the entire hierarchical structure and re-computing all costs in the structure to account for the changed cost of the sub-assembly. Since hierarchical structures may include thousands of nodes, this approach can be both time-consuming and a less-than-optimal use of computing resources.
These problems become further compounded when data is drawn from multiple sources. In the end, the same set of data ends up being stored in multiple locations. Storing such data in multiple locations adds search complexity and wastes computing resources.
Data management approaches such as those discussed above are very cumbersome. These approaches often require the user to enter each leaf node manually into the tree. Often, employee information is stored in multiple databases; for example, employee information may be stored in a human resources database and also in an organizational flowchart database. An employee might share responsibilities between two separate departments and, as a result, might need to be added to multiple locations in the same tree. Adding the employee's information to each separate database or under each separate department becomes redundant.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.